//
// Created by ASUS on 2024/12/3/星期二.
//
#include <bits/stdc++.h>
using namespace std;


class SuffixArray {
	vector<int> sa,rk,height,tmp,oldrk,id;
	string s;
public:
	SuffixArray(string  ss) {
		int n = ss.size();
		this->s=" "+s;
		sa.resize(n+1);
		id.resize(n+1);
		rk.resize(n+1);
		oldrk.resize(n+1);
		tmp.resize(n+1);
		height.resize(n+1);

		int m=128;
		int p;
		vector<int> cnt(m+1,0);
		for (int i = 1; i <= n; i++) cnt[rk[i] = s[i]]++;
		for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
		for (int i = n; i >= 1; i--) sa[cnt[rk[i]]--] = i;

		for (int w = 1;; w <<= 1, m = p) {  // m = p 即为值域优化
			int cur = 0;
			for (int i = n - w + 1; i <= n; i++) id[++cur] = i;
			for (int i = 1; i <= n; i++)
				if (sa[i] > w) id[++cur] = sa[i] - w;

			fill(cnt.begin(), cnt.end(), 0);
			for (int i = 1; i <= n; i++) cnt[rk[i]]++;
			for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
			for (int i = n; i >= 1; i--) sa[cnt[rk[id[i]]]--] = id[i];

			p = 0;
			oldrk=rk;
			for (int i = 1; i <= n; i++) {
				if (oldrk[sa[i]] == oldrk[sa[i - 1]] &&
				    oldrk[sa[i] + w] == oldrk[sa[i - 1] + w])
					rk[sa[i]] = p;
				else
					rk[sa[i]] = ++p;
			}

			if (p == n) break;  // p = n 时无需再排序
		}

		for(int i=1;i<=n;i++){
			rk[sa[i]]=i;
		}
	}

	vector<int> get_sa(){
		return sa;
	}
	vector<int> get_rk(){
		return rk;
	}
	vector<int> get_height(){
		int n=height.size()-1;
		for(int i=1,k=0;i<=n;i++){
			if(rk[i]==0) continue;
			if(k)k--;
			int j=sa[rk[i]-1];
			while(i+k<n&&j+k<n&&s[i+k]==s[j+k]) k++;
			height[rk[i]]=k;
		}
		return height;
	}
};
